{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Skips to Arrive at Meeting On Time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSkips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #准时抵达会议现场的最小跳过休息次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>hoursBefore</code> ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 <code>n</code> 条道路。道路的长度用一个长度为 <code>n</code> 的整数数组 <code>dist</code> 表示，其中 <code>dist[i]</code> 表示第 <code>i</code> 条道路的长度（单位：<strong>千米</strong>）。另给你一个整数 <code>speed</code> ，表示你在道路上前进的速度（单位：<strong>千米每小时</strong>）。</p>\n",
    "\n",
    "<p>当你通过第 <code>i</code> 条路之后，就必须休息并等待，直到 <strong>下一个整数小时</strong> 才能开始继续通过下一条道路。注意：你不需要在通过最后一条道路后休息，因为那时你已经抵达会议现场。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果你通过一条道路用去 <code>1.4</code> 小时，那你必须停下来等待，到 <code>2</code> 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 <code>2</code> 小时，就无需等待，可以直接继续。</li>\n",
    "</ul>\n",
    "\n",
    "<p>然而，为了能准时到达，你可以选择 <strong>跳过</strong> 一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，假设通过第 <code>1</code> 条道路用去 <code>1.4</code> 小时，且通过第 <code>2</code> 条道路用去 <code>0.6</code> 小时。跳过第 <code>1</code> 条道路的休息时间意味着你将会在恰好 <code>2</code> 小时完成通过第 <code>2</code> 条道路，且你能够立即开始通过第 <code>3</code> 条道路。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回准时抵达会议现场所需要的 <strong>最小跳过次数</strong> ，如果 <strong>无法准时参会</strong> ，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dist = [1,3,2], speed = 4, hoursBefore = 2\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "不跳过任何休息时间，你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。\n",
    "可以跳过第 1 次休息时间，共用 ((1/4 + <strong>0</strong>) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。\n",
    "注意，第 2 次休息时间缩短为 0 ，由于跳过第 1 次休息时间，你是在整数小时处完成通过第 2 条道路。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dist = [7,3,5,5], speed = 2, hoursBefore = 10\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "不跳过任何休息时间，你将用 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小时才能抵达会议现场。\n",
    "可以跳过第 1 次和第 3 次休息时间，共用 ((7/2 + <strong>0</strong>) + (3/2 + 0)) + ((5/2 + <strong>0</strong>) + (5/2)) = 10 小时抵达会议现场。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dist = [7,3,5,5], speed = 1, hoursBefore = 10\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>即使跳过所有的休息时间，也无法准时参加会议。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == dist.length</code></li>\n",
    "\t<li><code>1 <= n <= 1000</code></li>\n",
    "\t<li><code>1 <= dist[i] <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= speed <= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 <= hoursBefore <= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-skips-to-arrive-at-meeting-on-time](https://leetcode.cn/problems/minimum-skips-to-arrive-at-meeting-on-time/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-skips-to-arrive-at-meeting-on-time](https://leetcode.cn/problems/minimum-skips-to-arrive-at-meeting-on-time/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2]\\n4\\n2', '[7,3,5,5]\\n2\\n10', '[7,3,5,5]\\n1\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        dp = [0] + [inf] * (n := len(dist))\n",
    "        for i in range(1, n + 1):\n",
    "            cur = [inf] * (n + 1)\n",
    "            for j in range(i + 1):\n",
    "                if j != i:\n",
    "                    cur[j] = min(cur[j], ((dp[j] + dist[i - 1] - 1) // speed + 1) * speed)\n",
    "                if j:\n",
    "                    cur[j] = min(cur[j], dp[j - 1] + dist[i - 1])\n",
    "            dp = cur\n",
    "        for j in range(n + 1):\n",
    "            if dp[j] <= hoursBefore * speed:\n",
    "                return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        f = [[inf] * (n + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        eps = 1e-8\n",
    "        for i, x in enumerate(dist, 1):\n",
    "            for j in range(i + 1):\n",
    "                if j < i:\n",
    "                    f[i][j] = min(f[i][j], ceil(f[i - 1][j] + x / speed - eps))\n",
    "                if j:\n",
    "                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + x / speed)\n",
    "        for j in range(n + 1):\n",
    "            if f[n][j] <= hoursBefore + eps:\n",
    "                return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        f = [[inf] * (n + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        for i, x in enumerate(dist, 1):\n",
    "            for j in range(i + 1):\n",
    "                if j < i:\n",
    "                    f[i][j] = min(f[i][j], ((f[i - 1][j] + x - 1) // speed + 1) * speed)\n",
    "                if j:\n",
    "                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + x)\n",
    "        for j in range(n + 1):\n",
    "            if f[n][j] <= hoursBefore * speed:\n",
    "                return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        # 可忽略误差\n",
    "        EPS = 1e-7\n",
    "        \n",
    "        n = len(dist)\n",
    "        f = [[float(\"inf\")] * (n + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0.\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1):\n",
    "                if j != i:\n",
    "                    f[i][j] = min(f[i][j], ceil(f[i - 1][j] + dist[i - 1] / speed - EPS))\n",
    "                if j != 0:\n",
    "                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1] / speed)\n",
    "        \n",
    "        for j in range(n + 1):\n",
    "            if f[n][j] < hoursBefore + EPS:\n",
    "                return j\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        hoursBefore *= speed\n",
    "\n",
    "        total = sum(dist)\n",
    "        if total > hoursBefore:\n",
    "            return -1\n",
    "\n",
    "        dp = [[int(1e9)] * (n + 2) for i in range(n + 1)]\n",
    "        dp[0][1] = 0\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for skip in range(1, i + 2):\n",
    "                if i == n:\n",
    "                    dp[i][skip] = dp[i - 1][skip] + dist[i - 1]\n",
    "                else:\n",
    "                    dp[i][skip] = min(\n",
    "                        ((dp[i - 1][skip] + dist[i - 1] - 1) // speed + 1) * speed,\n",
    "                        dp[i - 1][skip - 1] + dist[i - 1]\n",
    "                    )\n",
    "        \n",
    "        for x in range(1, n + 2):\n",
    "            if dp[n][x] <= hoursBefore:\n",
    "                return x - 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        if sum(dist)/speed>hoursBefore:\n",
    "            return -1 \n",
    "        \n",
    "        n = len(dist)\n",
    "        dp = [[float(\"inf\")]*(n+1) for _ in range(n)]\n",
    "\n",
    "        EPS = 1e-9\n",
    "\n",
    "        dp[0][0] = math.ceil(dist[0]/speed-EPS)\n",
    "        dp[0][1] = dist[0]/speed\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+2):\n",
    "                if j==0:\n",
    "                    x = math.ceil(dp[i-1][j]+dist[i]/speed-EPS)\n",
    "                    dp[i][j] = x\n",
    "              \n",
    "                    continue \n",
    "                if j==i+1:\n",
    "                    x = dp[i-1][j-1]+dist[i]/speed\n",
    "                   \n",
    "                    dp[i][j] = x\n",
    "        \n",
    "                    continue\n",
    "                x = math.ceil(dp[i-1][j]+dist[i]/speed-EPS)\n",
    "\n",
    "                dp[i][j] = min(x, \n",
    "                    dp[i-1][j-1]+dist[i]/speed)\n",
    "\n",
    "        \n",
    "\n",
    "        # for i in range(n):\n",
    "        #     print(dp[i])\n",
    "        for j in range(n+1):\n",
    "            if dp[n-1][j]<=hoursBefore+EPS:\n",
    "                return j \n",
    "        return -1 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        eps = 10 ** -8\n",
    "        n = len(dist)\n",
    "        f = [[hoursBefore + 1] * n for _ in range(n)]\n",
    "\n",
    "        f[0][0] = dist[0] / speed\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i + 1):\n",
    "                time = dist[i] / speed\n",
    "                f[i][j] = min(math.ceil(f[i - 1][j] - eps) + time, f[i - 1][j - 1] + time)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if f[n - 1][i] <= hoursBefore + eps:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        f = [[float(\"inf\")] * (n + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1):\n",
    "                if j != i:\n",
    "                    f[i][j] = min(f[i][j], ((f[i - 1][j] + dist[i - 1] - 1) // speed + 1) * speed)\n",
    "                if j != 0:\n",
    "                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1])\n",
    "        \n",
    "        for j in range(n + 1):\n",
    "            if f[n][j] <= hoursBefore * speed:\n",
    "                return j\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        if sum(dist)/speed>hoursBefore:\n",
    "            return -1 \n",
    "        \n",
    "        n = len(dist)\n",
    "        dp = [[float(\"inf\")]*(n+1) for _ in range(n)]\n",
    "\n",
    "        EPS = 1e-9\n",
    "\n",
    "        dp[0][0] = math.ceil(dist[0]/speed-EPS)\n",
    "        dp[0][1] = dist[0]/speed\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+2):\n",
    "                if j==0:\n",
    "                    x = math.ceil(dp[i-1][j]+dist[i]/speed-EPS)\n",
    "                    dp[i][j] = x\n",
    "              \n",
    "                    continue \n",
    "                if j==i+1:\n",
    "                    x = dp[i-1][j-1]+dist[i]/speed\n",
    "                   \n",
    "                    dp[i][j] = x\n",
    "        \n",
    "                    continue\n",
    "                x = math.ceil(dp[i-1][j]+dist[i]/speed-EPS)\n",
    "\n",
    "                dp[i][j] = min(x, \n",
    "                    dp[i-1][j-1]+dist[i]/speed)\n",
    "\n",
    "        \n",
    "\n",
    "        # for i in range(n):\n",
    "        #     print(dp[i])\n",
    "        for j in range(n+1):\n",
    "            if dp[n-1][j]<=hoursBefore+EPS:\n",
    "                return j \n",
    "        return -1 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        def ceil(x):\n",
    "            ans = int(x)\n",
    "            ans += ans < x\n",
    "            return ans\n",
    "\n",
    "        eps = 10 ** -8\n",
    "        n = len(dist)\n",
    "        f = [[hoursBefore + 1] * n for _ in range(n)]\n",
    "\n",
    "        f[0][0] = dist[0] / speed\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i + 1):\n",
    "                time = dist[i] / speed\n",
    "                f[i][j] = min(ceil(f[i - 1][j] - eps) + time, f[i - 1][j - 1] + time)\n",
    "        \n",
    "        print(f[n - 1])\n",
    "        for i in range(n):\n",
    "            if f[n - 1][i] <= hoursBefore + eps:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        hoursBefore *= speed\n",
    "\n",
    "        n = len(dist)\n",
    "\n",
    "        dp = [[inf] * (n + 1) for _ in range(n)]\n",
    "        \n",
    "        for j in range(n + 1):\n",
    "            dp[0][j] = dist[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(n + 1):\n",
    "                t1 = dp[i - 1][j]\n",
    "\n",
    "                if t1 % speed != 0:\n",
    "                    t1 += speed - t1 % speed\n",
    "\n",
    "                dp[i][j] = t1 + dist[i]\n",
    "\n",
    "                if j > 0:\n",
    "                    t2 = dp[i - 1][j - 1]\n",
    "                    dp[i][j] = min(dp[i][j], t2 + dist[i])\n",
    "\n",
    "        for j in range(n + 1):\n",
    "            if dp[n - 1][j] <= hoursBefore:\n",
    "                return j\n",
    "\n",
    "        return -1 \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        if sum(dist) > hoursBefore * speed:\n",
    "            return -1\n",
    "        \n",
    "        def helper(x, y):\n",
    "            if x % y == 0:\n",
    "                return x\n",
    "            else:\n",
    "                return y * (x // y + 1)\n",
    "\n",
    "        dp = [[inf] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i, d in enumerate(dist, 1):\n",
    "            dp[i][0] = helper(dp[i - 1][0] + d, speed)\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = min(dp[i - 1][j - 1] + d, helper(dp[i - 1][j] + d, speed))\n",
    "\n",
    "        for j in range(n):\n",
    "            if dp[-1][j] <= hoursBefore * speed:\n",
    "                return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        dp = [[0] * (len(dist) + 1) for _ in range(len(dist))]\n",
    "        for i in range(1, len(dist) + 1):\n",
    "            if dp[0][i - 1] % speed != 0:\n",
    "                dp[0][i] = - (dp[0][i - 1] % speed) + dp[0][i - 1] + dist[i - 1] + speed\n",
    "            else:\n",
    "                dp[0][i] = dp[0][i - 1] + dist[i - 1]\n",
    "        if dp[0][-1] <= hoursBefore * speed:\n",
    "            return 0\n",
    "        for i in range(1, len(dist)):\n",
    "            for j in range(1, len(dist) + 1):\n",
    "                if dp[i][j - 1] % speed != 0:\n",
    "                    dp[i][j] = - (dp[i][j - 1] % speed) + dp[i][j - 1] + dist[j - 1] + speed\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1] + dist[j - 1]\n",
    "                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + dist[j - 1])\n",
    "            if dp[i][-1] <= hoursBefore * speed:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "\n",
    "        cost = [Decimal(d)/Decimal(speed) for d in dist]\n",
    "        n = len(dist)\n",
    "        dp = [[hoursBefore*2]*(n+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, n):\n",
    "\n",
    "            dp[i][0] = dp[i-1][0] + math.ceil(cost[i-1])\n",
    "            for j in range(1, i):\n",
    "                a, b = dp[i-1][j-1] + cost[i-1], math.ceil(dp[i-1][j] + cost[i-1])\n",
    "                dp[i][j] = a if a < b else b\n",
    "\n",
    "            dp[i][i] = dp[i-1][i-1] + cost[i-1]\n",
    "\n",
    "        for j in range(n+1):\n",
    "            if dp[n-1][j] + cost[-1] <= hoursBefore:\n",
    "                return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        if sum(dist) > hoursBefore * speed:\n",
    "            return -1\n",
    "\n",
    "        def cal(x, y):\n",
    "            return x if x % y == 0 else y * (x // y + 1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, re):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            # 不跳过休息时间, 则需 \"向上取整\"\n",
    "            res = cal(dist[idx] + dfs(idx + 1, re), speed)\n",
    "            if re:\n",
    "                res = min(res, dist[idx] + dfs(idx + 1, re - 1))\n",
    "            return res\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dfs(0, i) <= hoursBefore * speed:\n",
    "                ans = i\n",
    "                break\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        if sum(dist) > hoursBefore * speed:\n",
    "            return -1\n",
    "\n",
    "        def cal(x, y):\n",
    "            return x if x % y == 0 else y * (x // y + 1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, re):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            # 不跳过休息时间, 则需 \"向上取整\"\n",
    "            res = cal(dist[idx] + dfs(idx + 1, re), speed)\n",
    "            if re:\n",
    "                res = min(res, dist[idx] + dfs(idx + 1, re - 1))\n",
    "            return res\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dfs(0, i) <= hoursBefore * speed:\n",
    "                ans = i\n",
    "                break\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        if sum(dist) > hoursBefore * speed:\n",
    "            return -1\n",
    "\n",
    "        def cal(x, y):\n",
    "            return x if x % y == 0 else y * (x // y + 1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, re):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            # 不跳过休息时间, 则需 \"向上取整\"\n",
    "            res = cal(dist[idx] + dfs(idx + 1, re), speed)\n",
    "            if re:\n",
    "                res = min(res, dist[idx] + dfs(idx + 1, re - 1))\n",
    "            return res\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dfs(0, i) <= hoursBefore * speed:\n",
    "                ans = i\n",
    "                break\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        if sum(dist) > hoursBefore * speed:\n",
    "            return -1\n",
    "\n",
    "        def cal(x, y):\n",
    "            if x % y == 0:\n",
    "                return x\n",
    "            else:\n",
    "                return y * (x // y + 1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, re):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "\n",
    "            res = cal(dist[idx] + dfs(idx + 1, re), speed)\n",
    "            if re: \n",
    "                res = min(res, dist[idx] + dfs(idx + 1, re - 1))\n",
    "            return res\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dfs(0, i) <= hoursBefore * speed:\n",
    "                ans = i\n",
    "                break\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        if sum(dist) > hoursBefore * speed:\n",
    "            return -1\n",
    "\n",
    "        def cal(x, y):\n",
    "            return x if x % y == 0 else y * (x // y + 1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, re):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            # 不跳过休息时间, 则需 \"向上取整\"\n",
    "            res = cal(dist[idx] + dfs(idx + 1, re), speed)\n",
    "            if re:\n",
    "                res = min(res, dist[idx] + dfs(idx + 1, re - 1))\n",
    "            return res\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dfs(0, i) <= hoursBefore * speed:\n",
    "                ans = i\n",
    "                break\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class FloatToFrac:\n",
    "    def __init__(self):\n",
    "        # 将浮点数运算转换为分数计算\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def frac_add(frac1: List[int], frac2: List[int]) -> List[int]:\n",
    "        # 要求分母a1与a2均不为0\n",
    "        b1, a1 = frac1\n",
    "        b2, a2 = frac2\n",
    "        a = math.lcm(a1, a2)\n",
    "        b = b1 * (a // a1) + b2 * (a // a2)\n",
    "        g = math.gcd(b, a)\n",
    "        b //= g\n",
    "        a //= g\n",
    "        if a < 0:\n",
    "            a *= -1\n",
    "            b *= -1\n",
    "        return [b, a]\n",
    "\n",
    "    @staticmethod\n",
    "    def frac_max(frac1: List[int], frac2: List[int]) -> List[int]:\n",
    "        # 要求分母a1与a2均不为0\n",
    "        b1, a1 = frac1\n",
    "        b2, a2 = frac2\n",
    "        if a1 < 0:\n",
    "            a1 *= -1\n",
    "            b1 *= -1\n",
    "        if a2 < 0:\n",
    "            a2 *= -1\n",
    "            b2 *= -1\n",
    "        if b1 * a2 < b2 * a1:\n",
    "            return [b2, a2]\n",
    "        return [b1, a1]\n",
    "\n",
    "    @staticmethod\n",
    "    def frac_min(frac1: List[int], frac2: List[int]) -> List[int]:\n",
    "        # 要求分母a1与a2均不为0\n",
    "        b1, a1 = frac1\n",
    "        b2, a2 = frac2\n",
    "        if a1 < 0:\n",
    "            a1 *= -1\n",
    "            b1 *= -1\n",
    "        if a2 < 0:\n",
    "            a2 *= -1\n",
    "            b2 *= -1\n",
    "        if b1 * a2 > b2 * a1:\n",
    "            return [b2, a2]\n",
    "        return [b1, a1]\n",
    "\n",
    "    @staticmethod\n",
    "    def frac_ceil(frac: List[int]) -> int:\n",
    "        # 要求分母a1与a2均不为0\n",
    "        b, a = frac\n",
    "        return math.ceil(b / a)\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        if sum(dist) > hoursBefore * speed:\n",
    "            return -1\n",
    "\n",
    "        ff = FloatToFrac()\n",
    "        dp = [[[hoursBefore * 2, 1] for _ in range(n + 1)] for _ in range(n)]\n",
    "        dp[0][0] = [0, 1]\n",
    "        for i in range(n - 1):\n",
    "            dp[i + 1][0] = ff.frac_add(dp[i][0], [ff.frac_ceil([dist[i], speed]), 1])\n",
    "            for j in range(1, i + 2):\n",
    "                pre1 = [ff.frac_ceil(ff.frac_add(dp[i][j], [dist[i], speed])), 1]\n",
    "                pre2 = ff.frac_add(dp[i][j - 1], [dist[i], speed])\n",
    "                dp[i + 1][j] = ff.frac_min(pre1, pre2)\n",
    "        for j in range(n + 1):\n",
    "            cur = ff.frac_add(dp[n - 1][j], [dist[n - 1], speed])\n",
    "            if cur[0] <= hoursBefore * cur[1]:\n",
    "                return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        \"\"\"\n",
    "        :param dist:\n",
    "        :param speed:\n",
    "        :param hoursBefore:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        self.m = math.inf\n",
    "        if math.ceil(sum(dist) / speed) > hoursBefore:\n",
    "            return -1\n",
    "        ll = [math.ceil(i / speed) for i in dist]\n",
    "        if sum(ll) <= hoursBefore:\n",
    "            return 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def getCnt(idx, tused):\n",
    "            if idx >= len(dist):\n",
    "                if tused > hoursBefore:\n",
    "                    return math.inf\n",
    "                return 0\n",
    "            cur = dist[idx]\n",
    "            sum1 = cur\n",
    "            ans = math.ceil(cur / speed)\n",
    "            v1 = math.inf\n",
    "            if tused + ans <= hoursBefore:\n",
    "                v1 = getCnt(idx + 1, tused + ans)\n",
    "            v2 = math.inf\n",
    "            for i in range(idx + 1, min(len(dist), idx+15)):\n",
    "                sum1 += dist[i]\n",
    "                sk = i - idx\n",
    "                if tused + math.ceil(sum1 / speed) > hoursBefore:\n",
    "                    break\n",
    "                ans1 = sk + getCnt(idx + sk + 1,    tused + math.ceil(sum1 / speed))\n",
    "                v2 = min(v2, ans1)\n",
    "                if sum1 % speed == 0:\n",
    "                    break\n",
    "                \n",
    "            return min(v1, v2)\n",
    "\n",
    "        ans = getCnt(0,  0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        \"\"\"\n",
    "        :param dist:\n",
    "        :param speed:\n",
    "        :param hoursBefore:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        self.m = math.inf\n",
    "        if math.ceil(sum(dist) / speed) > hoursBefore:\n",
    "            return -1\n",
    "        ll = [math.ceil(i / speed) for i in dist]\n",
    "        if sum(ll) <= hoursBefore:\n",
    "            return 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def getCnt(idx, tused):\n",
    "            if idx >= len(dist):\n",
    "                if tused > hoursBefore:\n",
    "                    return math.inf\n",
    "                return 0\n",
    "            cur = dist[idx]\n",
    "            sum1 = cur\n",
    "            ans = math.ceil(cur / speed)\n",
    "            v1 = math.inf\n",
    "            if tused + ans <= hoursBefore:\n",
    "                v1 = getCnt(idx + 1, tused + ans)\n",
    "            v2 = math.inf\n",
    "            for i in range(idx + 1, min(len(dist), idx+15)):\n",
    "                sum1 += dist[i]\n",
    "                sk = i - idx\n",
    "                if tused + math.ceil(sum1 / speed) > hoursBefore:\n",
    "                    break\n",
    "                ans1 = sk + getCnt(idx + sk + 1, tused + math.ceil(sum1 / speed))\n",
    "                v2 = min(v2, ans1)\n",
    "                if sum1 % speed == 0:\n",
    "                    break\n",
    "\n",
    "            return min(v1, v2)\n",
    "        ans = getCnt(0,  0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        \"\"\"\n",
    "        :param dist:\n",
    "        :param speed:\n",
    "        :param hoursBefore:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        self.m = math.inf\n",
    "        if math.ceil(sum(dist) / speed) > hoursBefore:\n",
    "            return -1\n",
    "        ll = [math.ceil(i / speed) for i in dist]\n",
    "        if sum(ll) <= hoursBefore:\n",
    "            return 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def getCnt(idx, tused):\n",
    "            if idx >= len(dist):\n",
    "                if tused > hoursBefore:\n",
    "                    return math.inf\n",
    "                return 0\n",
    "            cur = dist[idx]\n",
    "            sum1 = cur\n",
    "            ans = math.ceil(cur / speed)\n",
    "            v1 = math.inf\n",
    "            if tused + ans <= hoursBefore:\n",
    "                v1 = getCnt(idx + 1, tused + ans)\n",
    "            v2 = math.inf\n",
    "            for i in range(idx + 1, min(len(dist), idx+20)):\n",
    "                sum1 += dist[i]\n",
    "                sk = i - idx\n",
    "                if tused + math.ceil(sum1 / speed) > hoursBefore:\n",
    "                    break\n",
    "                ans1 = sk + getCnt(idx + sk + 1,    tused + math.ceil(sum1 / speed))\n",
    "                v2 = min(v2, ans1)\n",
    "                if sum1 % speed == 0:\n",
    "                    break\n",
    "                \n",
    "            return min(v1, v2)\n",
    "\n",
    "        ans = getCnt(0,  0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "\n",
    "        def cal(x, y):\n",
    "            return x if x % y == 0 else y * (x // y + 1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, re):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            # 不跳过休息时间, 则需 \"向上取整\"\n",
    "            res = cal(dist[idx] + dfs(idx + 1, re), speed)\n",
    "            if re:\n",
    "                res = min(res, dist[idx] + dfs(idx + 1, re - 1))\n",
    "            return res\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dfs(0, i) <= hoursBefore * speed:\n",
    "                ans = i\n",
    "                break\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:\n",
    "        n = len(dist)\n",
    "        hoursBefore *= speed\n",
    "\n",
    "        total = sum(dist)\n",
    "        if total > hoursBefore:\n",
    "            return -1\n",
    "\n",
    "        @cache\n",
    "        def dp(i, skip):\n",
    "            if i == n - 1:\n",
    "                return dp(i - 1, skip) + dist[i]\n",
    "\n",
    "            if not 0 <= skip <= i + 1:\n",
    "                return int(1e9)\n",
    "\n",
    "            if i == -1:\n",
    "                if skip == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return int(1e9)\n",
    "\n",
    "            ret = min(\n",
    "                ((dp(i - 1, skip) + dist[i] - 1) // speed + 1) * speed,\n",
    "                dp(i - 1, skip - 1) + dist[i]\n",
    "            )\n",
    "\n",
    "            print(i, skip, ret)\n",
    "\n",
    "            return ret\n",
    "\n",
    "        for x in range(n + 1):\n",
    "            print(x, dp(n - 1, x))\n",
    "            if dp(n - 1, x) <= hoursBefore:\n",
    "                return x\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
